package leetcode

import (
	"container/heap"
	"fmt"
	"strconv"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

func (l *ListNode) String() string {
	var arr []interface{}
	for l != nil {
		arr = append(arr, strconv.FormatInt(int64((*l).Val), 10))
		l = l.Next
	}
	return fmt.Sprintf("%v", arr)
}

//两数字相加，每个数字是list存储的逆序数（head是个位数）：思路，进位，
//注意list 的结构体指针需要取其指针才能修改list结构体的指针
func addTwoNumbers1(l1 *ListNode, l2 *ListNode) *ListNode {
	var lr, lh *ListNode
	var carry int
	lr, carry = addTwoNode(&l1, &l2, 0)
	lh = lr
	for !(l1 == nil && l2 == nil && carry == 0) {
		lr.Next, carry = addTwoNode(&l1, &l2, carry)
		lr = lr.Next
	}
	return lh
}

func addTwoNode(n1 **ListNode, n2 **ListNode, car int) (*ListNode, int) {
	lr := new(ListNode)
	var carry int
	if *n1 == nil && *n2 != nil {
		lr.Val = ((*n2).Val + car) % 10
		carry = ((*n2).Val + car) / 10
		if (*n2).Next != nil {
			*n2 = (*n2).Next
		} else {
			*n2 = nil
		}
	} else if *n2 == nil && *n1 != nil {
		lr.Val = ((*n1).Val + car) % 10
		carry = ((*n1).Val + car) / 10
		if (*n1).Next != nil {
			*n1 = (*n1).Next
		} else {
			*n1 = nil
		}

	} else if *n1 != nil && *n2 != nil {
		lr.Val = ((*n1).Val + (*n2).Val + car) % 10
		carry = ((*n1).Val + (*n2).Val + car) / 10
		if (*n1).Next != nil {
			*n1 = (*n1).Next
		} else {
			*n1 = nil
		}
		if (*n2).Next != nil {
			*n2 = (*n2).Next
		} else {
			*n2 = nil
		}
	} else {
		lr.Val = (car) % 10
		carry = (car) / 10
	}
	return lr, carry
}

//另一种思路，先对齐，再相加
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	//去除l1和l2为空的特殊情况
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	//用两个能过对齐的链表来替代
	l1temp, l2temp := l1, l2
	for l1temp.Next != nil || l2temp.Next != nil {
		if l1temp.Next == nil {
			l1temp.Next = new(ListNode)
			l1temp.Next.Val = 0
		}
		if l2temp.Next == nil {
			l2temp.Next = new(ListNode)
			l2temp.Next.Val = 0
		}
		l1temp = l1temp.Next
		l2temp = l2temp.Next
	}

	carry := 0          //表示进位
	lr := new(ListNode) //计算结果链表
	head := lr          //先弄个哨兵
	for ; l1 != nil; l1 = l1.Next {
		lr.Next = new(ListNode)
		lr = lr.Next

		lr.Val = (carry + l1.Val + l2.Val) % 10
		carry = (carry + l1.Val + l2.Val) / 10

		l2 = l2.Next
	}
	if carry != 0 {
		lr.Next = &ListNode{
			Val:  carry,
			Next: nil,
		}
	}
	return head.Next
}

//反转链表，一个一个往前面添加
func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	lr := &ListNode{
		Val:  head.Val,
		Next: nil,
	}
	for head.Next != nil {
		temp := &ListNode{
			Val:  head.Next.Val,
			Next: lr,
		}
		head = head.Next
		lr = temp
	}
	return lr
}

func reverseList2(head *ListNode) *ListNode {
	var pre *ListNode
	cur := head
	for cur != nil {
		tmp := cur.Next
		cur.Next = pre
		pre = cur
		cur = tmp
	}
	return cur
}

//检测链表里是否有环，两个速度不一样的遍历，看最终是否能重合
func hasCycle(head *ListNode) bool {
	if head == nil {
		return false
	}
	ln := head
	for ln.Next != nil && ln.Next.Next != nil {
		ln = ln.Next.Next
		head = head.Next
		if ln == head {
			return true
		}
	}
	return false
}

//142. 环形链表 II
func detectCycle(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	ln1, ln2 := head, head
	for ln1.Next != nil && ln2.Next.Next != nil {
		ln1 = ln1.Next
		ln2 = ln2.Next.Next

		if ln1 == ln2 {
			ln2 = head
			for ln2 != ln1 {
				ln2 = ln2.Next
				ln1 = ln1.Next
			}
			return ln1
		}
	}
	return nil
}

//合并两个有序的链表，思路同归并排序里面的合并
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	lr := new(ListNode)
	head := lr
	for l1 != nil && l2 != nil {
		if l1.Val <= l2.Val {
			lr.Next = l1
			l1 = l1.Next
		} else {
			lr.Next = l2
			l2 = l2.Next
		}
		lr = lr.Next
	}
	if l1 != nil {
		lr.Next = l1
	}
	if l2 != nil {
		lr.Next = l2
	}
	return head.Next
}

//删除倒数第n个值，思路：前后相隔n遍历，然后先开始遍历那个到了头，删除后面遍历的那个节点即可
//注意head的特殊性，要在前面加一个哨兵，因为可能会删除head
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	l1 := head
	l2 := &ListNode{
		Val:  0,
		Next: head,
	}
	cnt := 0
	for l1 != nil {
		l1 = l1.Next
		cnt++
		if cnt > n {
			l2 = l2.Next
		}
	}
	if l2.Next != nil {
		//考虑到head的特殊性
		if l2.Next == head {
			head = l2.Next.Next
		} else {
			l2.Next = l2.Next.Next
		}
	}
	return head
}

//找中间节点，思路还是前后两个速度遍历链表
func middleNode(head *ListNode) *ListNode {
	l1 := head
	l2 := head
	for l1.Next != nil && l1.Next.Next != nil {
		l1 = l1.Next.Next
		l2 = l2.Next
	}
	if l1.Next != nil {
		l2 = l2.Next
	}
	return l2
}

//25. K 个一组翻转链表
func reverseKGroup(head *ListNode, k int) *ListNode {
	temp := head
	nums := make([]int, 0)
	for temp != nil {
		nums = append(nums, temp.Val)
		temp = temp.Next
	}
	temp = head
	for i := 0; i+k-1 < len(nums); i = i + k {
		for j := i + k - 1; j >= i; j-- {
			temp.Val = nums[j]
			temp = temp.Next
		}
	}
	return head
}

func swapPairs(head *ListNode) *ListNode {
	sentinel := &ListNode{
		Val:  0,
		Next: head,
	}
	tmp := sentinel
	for tmp.Next != nil && tmp.Next.Next != nil {
		node1 := tmp.Next
		node2 := tmp.Next.Next
		tmp.Next = node2
		node1.Next = node2.Next
		node2.Next = node1
		tmp = tmp.Next.Next
	}
	return sentinel.Next
}

//优先级队列
func mergeKLists(lists []*ListNode) *ListNode {
	mk := &mergeK{make([]*ListNode, 0)}
	for i := range lists {
		if lists[i] != nil {
			mk.ls = append(mk.ls, lists[i])
		}
	}
	heap.Init(mk)
	if mk.Len() == 0 {
		return nil
	}
	head := heap.Pop(mk).(*ListNode)
	tmp := head
	if tmp.Next != nil {
		heap.Push(mk, tmp.Next)
	}
	for mk.Len() > 0 {
		p := heap.Pop(mk).(*ListNode)
		if p != nil {
			tmp.Next = p
		} else {
			break
		}
		tmp = tmp.Next
		if tmp.Next != nil {
			heap.Push(mk, tmp.Next)
		}
	}
	return head
}

type mergeK struct {
	ls []*ListNode
}

func (m *mergeK) Push(x interface{}) {
	m.ls = append(m.ls, x.(*ListNode))
}

func (m *mergeK) Pop() interface{} {
	n := m.Len()
	x := m.ls[n-1]
	m.ls = m.ls[:n-1]
	return x
}

func (m mergeK) Len() int {
	return len(m.ls)
}

func (m mergeK) Less(i, j int) bool {
	return m.ls[i].Val < m.ls[j].Val
}

func (m mergeK) Swap(i, j int) {
	m.ls[i], m.ls[j] = m.ls[j], m.ls[i]
}

//148. 排序链表
func sortList(head *ListNode) *ListNode {
	return sortListRecursion(head, nil)
}

func sortListRecursion(head, tail *ListNode) *ListNode {
	if head == nil {
		return head
	}
	//长度为1
	if head.Next == tail {
		head.Next = nil
		return head
	}
	slow, fast := head, head
	for fast != tail {
		slow = slow.Next
		fast = fast.Next
		if fast != tail {
			fast = fast.Next
		}
	}
	list := mergeList(sortListRecursion(head, slow), sortListRecursion(slow, tail))
	return list
}

func mergeList(head1, head2 *ListNode) *ListNode {
	nodeNew := &ListNode{}
	head := nodeNew
	for head1 != nil && head2 != nil {
		if head1.Val < head2.Val {
			nodeNew.Next = head1
			head1 = head1.Next
		} else {
			nodeNew.Next = head2
			head2 = head2.Next
		}
		nodeNew = nodeNew.Next
	}
	if head1 != nil {
		nodeNew.Next = head1
	}
	if head2 != nil {
		nodeNew.Next = head2
	}
	return head.Next
}

//160. 相交链表
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	if headA == nil || headB == nil {
		return nil
	}
	n1, n2 := headA, headB
	l1, l2 := 1, 1
	for n1.Next != nil {
		n1 = n1.Next
		l1++
	}
	for n2.Next != nil {
		n2 = n2.Next
		l2++
	}
	if n1 == n2 {
		n1, n2 = headA, headB
		if l1 > l2 {
			for k := l1 - l2; k > 0; k-- {
				n1 = n1.Next
			}
		} else {
			for k := l2 - l1; k > 0; k-- {
				n2 = n2.Next
			}
		}
		for n1 != nil && n2 != nil {
			if n1 == n2 {
				return n1
			}
			n1 = n1.Next
			n2 = n2.Next
		}
	}
	return nil
}

//234. 回文链表
func isPalindrome(head *ListNode) bool {
	slow, fast := head, head
	for fast != nil {
		slow = slow.Next
		fast = fast.Next
		if fast != nil {
			fast = fast.Next
		}
	}
	head2 := reverseList(slow)
	for head != nil {
		if head.Val != head2.Val {
			return false
		}
		head = head.Next
		head2 = head2.Next
	}
	return true
}

//1. 判定链表是否有环
func hasCircle(head *ListNode) bool {
	if head == nil {
		return false
	}
	slow, fast := head, head
	for fast != nil {
		slow = slow.Next
		fast = fast.Next
		if fast != nil {
			fast = fast.Next
		}
		if fast == slow {
			return true
		}
	}
	return false
}